Cryptography is the science of protecting information from eavesdropping and tampering and is often carried out by encrypting the information into an unreadable format. The encrypted information can then be stored or sent to a receiving party who can only read the information by decrypting the information into a readable format. Bit-commitment protocols are kinds of cryptographic procedures that can be followed by two or more mistrusting parties to exchange information. A number of different bit-commitment protocols that are based on encryption algorithms have been developed over the years.
Bit-commitment protocols are typically described with reference to two mistrusting parties, called “Alice” and “Bob,” who agree to exchange information in the form of bits. For example, Alice and Bob can use the state pair a bit (a two-state system), represented by “0” and “1,” to represent closed-question answers, such as “Yes” and “No,” or “True” and “False.” Alice and Bob can also use a bit string to encode information and a bit-commitment protocol to verify that each bit in the bit string has not been tampered with. Suppose, for example, that Alice is a stock broker who wants to sell Bob her stock tips. Alice wants to show Bob that she has a proven method for selecting stocks by sending him a list of stock tips before the stocks change. However, Alice does not want Bob to peek at the list and profit from her stock tips without first purchasing the tips. On the other hand, Bob wants to be sure that before Alice gives him the list of stock tips, Alice cannot revise her original list of stock tips after the stocks have changed. Both Alice and Bob may agree to use a bit-commitment protocol that employs an encryption algorithm to encrypt the stock tips and uses a private numeric key to decrypt the encrypted stock tips.
FIGS. 1A-1B illustrate two examples of bit-commitment protocols. Bit-commitment protocols are typically comprised of a commitment phase and a reveal phase. For example, in both FIGS. 1A-1B, the commitment phases correspond to solid-line directional arrows 102 and 103, and the reveal phases correspond to dashed-line directional arrows 104-106. In FIG. 1A, Alice completes the commitment phase by sending Bob the encrypted stock tips. At a later time, when the stocks have changed and Alice is ready to reveal the stock tips to Bob, Alice completes the reveal phase by sending the numeric key to Bob so that Bob can decrypt the encrypted stock tips and check whether the stock tips were indeed correct. In order for the bit-commitment protocol to operate properly, Alice cannot change her committed bit by choosing a different numeric key to send to Bob at the reveal phase. For an added level of security, Alice and Bob may agree to employ the services of a third party called “Trent.” In FIG. 1B, Alice again encrypts the stock tips using the encryption algorithm, but, in this protocol, Alice completes the commitment phase by sending the encrypted stock tips to Trent. Trent holds the encrypted stock tips until Alice is ready to reveal the stock tips to Bob. Alice completes the reveal phase by instructing Trent to send the encrypted stock tips to Bob and she sends the numeric key to Bob.
Bit-commitment protocols that rely on encryption algorithms and third parties, however, may not be reliable. The encryption algorithms often rely on unproven mathematical assumptions, such as one-way functions and pseudorandom number generators, and advancements in mathematics, computer science, and quantum computing may make it possible to decrypt encrypted information. For example, in the first example shown in FIG. 1A, Bob may possess an algorithm that allows him to decrypt the encrypted stock tips without the numeric key. In addition, a third party entrusted with holding encrypted information may be persuaded to conspire with one of the mistrusting parties. For example, in the second example shown in FIG. 1B, Trent may conspire with Alice so that Alice can encrypt tips on stocks that increased in value, or Trent may conspire with Bob by providing Bob with the encrypted stock tips so that Bob can decrypt the encrypted stock tips and purchase the stocks before the stocks change. Physicists, cryptologists, and computer scientists have recognized a need for methods and systems that can be used to execute bit-commitment protocols that are not based on encryption algorithms and the information held by the third party is not sufficient alone to determine the bit with certainty.